package com.zxy.leetcode._00000_00099._00000_00009;

/**
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 *
 * 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 标签：动态规划、字符串
 *
 * 思路
 * dp[i][j] 表示i到j之间的字符串是否是回文串
 * dp[i][j] = dp[i+1][j-1] and (s[i]==s[j])
 * 边界：当s[i]==s[j]，子串长度是2或3，不需要检查子串是否回文串，即j-i<=2
 */
public class Test00005 {

    public static void main(String[] args) {
        Test00005 test = new Test00005();
        System.out.println(test.longestPalindrome(""));
        System.out.println(test.longestPalindrome("a"));
        System.out.println(test.longestPalindrome("aa"));
        System.out.println(test.longestPalindrome("aaaa"));
        System.out.println(test.longestPalindrome("aba"));
        System.out.println(test.longestPalindrome("abba"));
        System.out.println(test.longestPalindrome("abc"));
        System.out.println(test.longestPalindrome("babad"));

    }

    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        int len = s.length();
        int maxLen = 1;
        int left = 0;
        int right = 0;
        boolean[][] dp = new boolean[len][len];
        char[] chars = s.toCharArray();

        // 如果i从0开始，那么对应abba这样的字符串，bb这个子串在遍历过程中没法被当做子问题进行存储
        for (int i=len-2; i>=0; i--) {
            for (int j=i+1; j<len; j++) {
                if (chars[i] == chars[j]) {
                    if (j-i <= 2) {     // 最小问题
                        if (j-i+1 > maxLen) {
                            maxLen = j-i+1;
                            left = i;
                            right = j;
                        }
                        dp[i][j] = true;
                    }else if (dp[i+1][j-1]) {   // 子问题
                        if (j-i+1 > maxLen) {
                            maxLen = j-i+1;
                            left = i;
                            right = j;
                        }
                        dp[i][j] = true;
                    }
                }
            }
        }

        return s.substring(left, right + 1);
    }

}
